
//130.被围绕的区域
class Solution {
public:
    void solve(vector<vector<char>>& nums) {
        //正难则反
        //直接将围绕区域的X变成O还需要判断,那不如直接将没有没围绕的进行标记,其余的没有被标记的不就是被围绕的嘛
        int n=nums.size(),m=nums[0].size();
        int dx[]={0,0,1,-1};
        int dy[]={1,-1,0,0};

        function<void(int,int)> dfs=[&](int x,int y)
        {
            nums[x][y]='I';
            for(int k=0;k<4;k++)
            {
                int a=x+dx[k],b=y+dy[k];
                if(a>=0&&a<n&&b>=0&&b<m&&nums[a][b]=='O') dfs(a,b);
            }
        };

        for(int i=0;i<n;i++)  //标记没有被包围的O
        {
            if(nums[i][0]=='O') dfs(i,0);
            if(nums[i][m-1]=='O') dfs(i,m-1);
        }
        for(int i=0;i<m;i++)
        {
            if(nums[0][i]=='O') dfs(0,i);
            if(nums[n-1][i]=='O') dfs(n-1,i);
        }

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(nums[i][j]=='O') nums[i][j]='X';
                else if(nums[i][j]=='I') nums[i][j]='O';
            }
        }
    }
};